/**
 * @file   main.cpp
 * @author Zhao jingting <jtzhao@Zhao jingting.
 * @date   The Nov 24 17:00:23 2021
 *
 * @brief  A program to test.
 *
 *
 */


#include"BalanceTree.h"
#include<vector>
#include<cstdlib>
#include<ctime>


template<typename T>
void Avl_sort(vector<T>& _data)
{
	AvlTree<int> Avl;
	int size = _data.size();
	for (int n = 0; n < size; n++)
	{
		Avl.insert(_data[n]);
	}
	//inorder traversal
	Avl.inorder();
	for (int n = 0; n < size; n++)
	{
		_data[n] = Avl.s.front();
		Avl.s.pop();
	}
	cout << "Number of calls to recursion: " << Avl.count_settree << endl;
}

template<typename T>
void Splay_sort(vector<T>& _data)
{
  SplayTree<int> tree ;
  	int size = _data.size();
	for (int n = 0; n < size; n++)
	{
	  	tree.insert(_data[n]);
	}
	
	//inorder traversal
	tree.inOrder();



	for (int n = 0; n < size; n++)
	{
		_data[n] = tree.s.front();
		tree.s.pop();
	}
	cout << "Number of calls to recursion or For loop: " << tree.count_settree << endl;
}

int main()
{
	srand(time(0));
	//进行顺序数列的效率测试
	cout << "-----------------------" << "For Inordered Series" << "--------------------------" << endl;
	//容器初始化
	vector<int> v1, v2;
	for (int n = 0; n < 30; n++)
	{
		v1.push_back(n);
		v2.push_back(n);
	}
	cout << "the origin Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v1[n] << " ";
	}
	cout << endl;
	//使用avltree排序
	Avl_sort(v1);
	cout << "after using Avl_sort the  Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v1[n] << " ";
	}
	cout << endl << "----------------------" << endl << endl;
	cout << "the origin Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v2[n] << " ";
	}
	cout << endl;
	//使用splay排序
	Splay_sort(v2);
	cout << "after using Splay_sort the  Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v2[n] << " ";
	}
	cout<<endl << "-----------------------------------------------------------------" << endl << endl << endl;
	//进行乱序数列效率测试
	cout << endl << "-----------------------" << "For random Series" << "--------------------------" << endl << endl;
	vector<int> v3, v4;
	//容器初始化
	for (int n = 0; n < 30; n++)
	{
		int a = rand()%3000;
		v3.push_back(a);
		v4.push_back(a);
	}
	cout << "the origin Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v3[n] << " ";
	}
	cout << endl;
	//使用avl排序
	Avl_sort(v3);
	cout << "after using Avl_sort the  Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v3[n] << " ";
	}
	cout << endl << "----------------------" << endl << endl;
	cout << "the origin Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v4[n] << " ";
	}
	cout << endl;
	//使用splaytree排序
	Splay_sort(v4);
	cout << "after using Splay_sort the  Vector: ";
	for (int n = 0; n < 30; n++)
	{
		cout << v4[n] << " ";
	}
	cout <<endl<< "-----------------------------------------------------------------" << endl;

}
